﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 原题连接：https://leetcode.cn/problems/majority-element-ii/description/
/*
题目描述：
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。



示例 1：

输入：nums = [3,2,3]
输出：[3]
示例 2：

输入：nums = [1]
输出：[1]
示例 3：

输入：nums = [1,2]
输出：[1,2]


提示：

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109


进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
*/

// 开始解题：
// 方法——摩尔斯投票法(模板写法)
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int, int> cands;
        int n = nums.size();
        int k = 3;
        for (auto x : nums) {
            if (cands.size() < k - 1) {
                cands[x]++;
            }
            else if (cands.count(x)) {
                cands[x]++;
            }
            else {
                vector<int> dels;
                for (auto& [key, val] : cands) {
                    if (--val == 0) {
                        dels.push_back(key);
                    }
                }
                for (auto e : dels) {
                    cands.erase(e);
                }
            }
        }
        vector<int> ret;
        for (auto& [key, val] : cands) {
            val = 0;
        }
        for (auto x : nums) {
            if (cands.count(x)) {
                cands[x]++;
            }
        }
        for (auto& [key, val] : cands) {
            if (val > n / k) {
                ret.push_back(key);
            }
        }
        return ret;
    }
};